package zoran.wang.doublepoint;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author wangzhuo
 * @time 2025-04-09-18:13
 */
public class SlidinWindow {

    /**
     * 最小覆盖子串
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {

        // 转数组方便下标操作
        char[] charArray = s.toCharArray();

        // 滑动窗口
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();

        // 将目标窗口存入到 HashMap<字符，出现的次数>
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
            window.put(c, 0);
        }

        // 记录滑动窗口内达到了次数的字符
        int valid = 0;

        // 记录最小覆盖子串的起点和长度
        int start = 0, len = Integer.MAX_VALUE;

        int left = 0, right = 0;
        // 滑动窗口，启动！
        while (right < s.length()) {

            // addChar 为进入滑动窗口的右端元素
            char addChar = charArray[right];
            // 增大窗口
            right++;

            // 如果c是need中的元素，添加到滑动窗口
            if (need.containsKey(addChar)) {
                window.put(addChar, window.get(addChar) + 1);

                // 如果c的数量达到了need中的次数，则记录+1
                if (window.get(addChar).equals(need.get(addChar))) valid++;
            }

            // 当window>need时，即valid满足了条件，缩小滑动窗口
            while (left < right && valid == need.size()) {

                // 如果此滑动窗口的长度小于之前的最小子串，则更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                // removeChar 是将移出窗口的元素
                char removeChar = charArray[left];
                // 缩小窗口
                left++;

                // 如果c是need中的元素，移出滑动窗口
                if (need.containsKey(removeChar)) {
                    // 移出之前判断一下有没有破坏valid
                    if (window.get(removeChar).equals(need.get(removeChar))) valid--;
                    window.put(removeChar, window.get(removeChar) - 1);
                }
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    @Test
    public void testMinWindow() {
        String s = minWindow("cabwefgewcwaefgcf", "cae");
        System.out.println(s);
    }

    /**
     * 字符串排列
     *
     * @param target
     * @param source
     * @return
     */
    public boolean checkInclusion(String target, String source) {

        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();

        // 将目标字符串 target 存入 need
        for (char c : target.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        // valid == need.size() 时满足滑动窗口的缩小条件
        int valid = 0;

        // 滑动窗口，启动！
        int left = 0, right = 0;
        while (right < source.length()) {

            // 增大窗口
            char addEle = source.charAt(right);
            right++;

            // 更新窗口以及 valid
            if (need.containsKey(addEle)) {
                window.put(addEle, window.getOrDefault(addEle, 0) + 1);
                if (need.get(addEle).equals(window.get(addEle))) valid++;
            }

            while (left < right && valid == need.size()) {

                //System.out.printf("window: [%d, %d)\n", left, right);

                // 更新结果
                if (right - left == target.length()) {
                    return true;
                }

                // 缩小窗口
                char removeEle = source.charAt(left);
                left++;

                // 更新窗口以及 valid
                if (need.containsKey(removeEle)) {
                    if (need.get(removeEle).equals(window.get(removeEle))) valid--;
                    window.put(removeEle, window.get(removeEle) - 1);
                }
            }
        }

        return false;
    }

    @Test
    public void testCheckInclusion() {

        boolean b = checkInclusion("abcdxabcde", "abcdeabcdx");
        System.out.println("b = " + b);
    }

    /**
     * 找到字符串中所有字母异位词
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {

        List<Integer> resultList = new ArrayList<>();

        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();

        for (char c : p.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        // r 停止条件
        int valid = 0;

        // 滑动窗口，启动！
        int l = 0, r = 0;
        while (r < s.length()) {

            // 增大窗口
            char addElement = s.charAt(r);
            r++;

            // 修改滑动窗口和 Valid
            if (need.containsKey(addElement)) {
                window.put(addElement, window.getOrDefault(addElement, 0) + 1);
                if (window.get(addElement).equals(need.get(addElement))) valid++;
            }

            while (l < r && valid == need.size()) {

                System.out.printf("window: [%d, %d)\n", l, r);

                // 判断条件
                if (r - l == p.length()) {
                    resultList.add(l);
                }

                // 缩小窗口
                char removeElement = s.charAt(l);
                l++;

                // 修改滑动窗口和 Valid
                if (need.containsKey(removeElement)) {
                    if (window.get(removeElement).equals(need.get(removeElement))) valid--;
                    window.put(removeElement, window.getOrDefault(removeElement, 0) - 1);
                }

            }
        }

        return resultList;
    }

    @Test
    public void testFindAnagrams() {

        List<Integer> anagrams = findAnagrams("cbaebabacd", "abc");
        anagrams.forEach(System.out::println);
    }

    /**
     * 无重复字符的最长子串
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {

        int length = 0;

        HashMap<Character, Integer> window = new HashMap<>();

        // 滑动窗口中是否存在重复元素
        boolean repeadFlag = false;

        // 滑动窗口，启动！
        int l = 0, r = 0;
        while (r < s.length()) {

            char addChar = s.charAt(r);
            r++;

            // 直接添加到滑动窗口中
            window.put(addChar, window.getOrDefault(addChar, 0) + 1);

            // 如果添加到相同的字母，则 r 停止，准备缩小窗口
            if (window.get(addChar) > 1) {
                repeadFlag = true;
            } else {
                // 如果没有，说明是最大子串，更新结果
                if (r - l > length) length = r - l;
                //System.out.println("l=" + l + "," + "r=" + r);
            }

            // 滑动窗口内有重复字符，缩小滑动窗口
            while (l < r && repeadFlag) {

                char removeChar = s.charAt(l);
                l++;

                window.put(removeChar, window.get(removeChar) - 1);

                // 删掉了这个重复元素，数量从2变成了1，更新valid，下次不会进入到该循环
                if (window.get(removeChar).equals(1)) {
                    repeadFlag = false;
                }
            }
        }

        return length;
    }

    @Test
    public void testLengthOfLongestSubstring() {

        int length = lengthOfLongestSubstring("");
        System.out.println("length = " + length);
    }
}